package bin_tree;

import java.util.NoSuchElementException;

/**
 * 基于int的二分搜索树，不包含重复元素
 */
public class BST {
    private Node root;
    //当前节点的个数
    private int size;
    //节点定义
    private class Node{
        private Node left;
        private Node right;
        private int val;

        public Node(int val) {
            this.val = val;
        }
    }
    public void add(int value){
        root=add(root,value);
    }

    /**
     * 向以root为根节点的BST中添加一个新元素value
     * @param root
     * @param value
     * @return 返回添加后的根节点
     */
    private Node add(Node root, int value) {
        if(root==null){
            Node node=new Node(value);
            size++;
            return node;
        }
        //比较value和根节点的大小
        if(value<root.val){
           root.left=add(root.left,value);
           return root;
        }
            root.right=add(root.right,value);
            return root;

    }

    /**
     * 查找BST中是否包含指定元素
     * @param val
     * @return
     */
    public boolean contains(int val){
        return contains(root,val);
    }

    /**
     * 判断以root为根节点的BST中是否存在val
     * @param root
     * @param val
     * @return
     */
    private boolean contains(Node root, int val) {
        if(root==null){
            return false;
        }else if(val==root.val){
            return true;
        }else if(val< root.val){
          return contains(root.left,val);
        }
        return contains(root.right,val);

    }

    //查找bst中的最大值
    public int maximum(){
        if(size==0){
           throw new NoSuchElementException("bst is empty!");
        }
        Node maxNode=maximum(root);
        return maxNode.val;
    }

    private Node maximum(Node root) {
        if(root.right==null){
            return root;
        }
        return maximum(root.right);
    }

    //查找bst中的最小值
    public int minimum(){
        if(size==0){
            throw new NoSuchElementException("bst is empty!");
        }
        Node minNode=minimum(root);
        return minNode.val;
    }

    private Node minimum(Node root) {
        if(root.left==null){
            return root;
        }
        return minimum(root.left);
    }

    /**
     * 删除bst中的最大值节点并返回值
     * @return
     */
    public int removeMax(){
        int val=maximum();
        root=removeMax(root);
        return val;

    }

    /**
     * 删除以当前root为根节点的BST的最大值节点
     * @param root
     * @return
     */
    private Node removeMax(Node root) {
        if(root.right==null){
            Node left=root.left;
            root.left=null;
            size--;
            return left;
        }
        root.right= removeMax(root.right);
        return root;
    }

    /**
     * 删除最小值节点并返回值
     * @return
     */
    public int removeMin(){
        int val =minimum();
        root=removeMin(root);
        return val;
    }

    /**
     * 删除以当前root为根节点的BST的最小值节点
     * @param root
     * @return
     */
    private Node removeMin(Node root) {
        if(root.left==null){
            //此时root为最小值节点
            //将右树返回
            Node right=root.right;
            //断枝
            root.right=null;
            size--;
            return right;
        }
        root.left= removeMin(root.left);
        return root;
    }

    /**
     * 删除BST中的任意元素
     * @param val
     */
    public void remove(int val){
        root=remove(root,val);
    }

    /**
     * Hibbard Deletion
     * 在以root为根节点的二叉树中删除值为val的节点
     * 返回删除后的根节点
     * @param root
     * @param val
     * @return
     */
    private Node remove(Node root, int val) {
        if(root==null){
            //遍历完BST也没找到值为val的结点
            return null;
        }else if(val<root.val){
            //在最左树中删除
            root.left=remove(root.left,val);
            return root;
        }else if(val>root.val){
            //在右树中删除
            root.right=remove(root.right,val);
            return root;
        }else {
            //此时root就是待删除的结点
            //判断其左右子树
            if(root.left==null){
                Node right=root.right;
                root.right=null;
                size--;
                return right;
            }
            if(root.right==null){
                Node left=root.left;
                root.left=null;
                size--;
                return left;
            }
            //此时说明root的左右子树都存在
            //找到root.right中的最小值
            Node successor=minimum(root.right);
            //successor就是root的后继结点
            successor.right=removeMin(root.right);
            successor.left=root.left;
            root.left=root.right=null;
            return successor;

        }
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }

    /**
     * 先序遍历二分搜索树
     * @param root
     * @param depth
     * @param sb
     */
    private void generateBSTString(Node root, int depth, StringBuilder sb) {
        if(root==null){
            sb.append(generateBSTDepth(depth)).append("NULL\n");
            return;
        }
        //先根节点
        sb.append(generateBSTDepth(depth)).append(root.val+"    \n");
        //递归访问左子树
        generateBSTString(root.left,depth+1,sb);
        //递归访问右子树
        generateBSTString(root.right,depth+1,sb);
    }

    private String generateBSTDepth(int depth) {
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}
